package day012;

import java.util.Scanner;

public class NQuene {

    static final int M = 105;
    static int n;
    static int[] x = new int[M];
    static int countn;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入皇后的个数n：");
        n = scanner.nextInt();

        backTrack(1);                                            //进行搜索
        System.out.println("答案的个数是：" + countn);
    }

    public static void backTrack(int t) {
        if (t > n) {
            countn++;
            for (int i = 1; i <= n; i++) {
                System.out.println(x[i] + " ");
            }
            System.out.println();
        } else {
            for (int i = 1; i <= n; i++) {
                x[t] = i;
                if (place(t)) {
                    backTrack(t + 1);
                }
            }
        }
    }

    public static boolean place(int t) {
        boolean ok = true;
        for (int j = 1; j < t; j++) {
            if (x[t] == x[j] || t - j == Math.abs(x[t] - x[j])) {
                ok = false;
                break;
            }
        }
        return ok;
    }
}
